package org.sylthas.algorithm;

import java.util.Arrays;

/**
 * 排序算法
 * 
 * @author Sylthas
 *
 */
public class SortAlgorithm {

    /**
     * 冒泡排序
     * 
     * @param arr
     */
    void bubbleSort(int[] arr) {
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            for (int k = 0; k < len - 1; k++) {
                if (arr[k] > arr[k + 1]) {
                    int temp = arr[k];
                    arr[k] = arr[k + 1];
                    arr[k + 1] = temp;
                }
            }
        }
    }

    /**
     * 快速排序
     * 
     * @param arr 数组
     * @param left 开始索引
     * @param right 结束索引
     */
    void quickSort(int[] arr, int left, int right) {
        int l, r, m, temp;
        l = left;
        r = right;
        m = arr[(l + r) / 2];
        do {
            // 找出左边比中间大的数
            while (arr[l] < m && l++ < right)
                ;
            // 找出右边比中间小的数
            while (arr[r] > m && r-- > left)
                ;
            // 左右交换
            if (l <= r) {
                temp = arr[l];
                arr[l] = arr[r];
                arr[r] = temp;
                l++;
                r--;
            }
        } while (l <= r);
        if (l < right) {
            quickSort(arr, l, right);
        }
        if (r > left) {
            quickSort(arr, left, r);
        }

    }

    /**
     * 二分法查找
     * 
     * @param sc 有序数组
     * @param t 目标
     * @param s 开始索引
     * @param e 结束索引
     * @return
     */
    int bSearch(int sc[], int t, int s, int e) {
        int m = (s + e) / 2;
        if (sc[m] == t)
            return m;
        if (sc[m] < t)
            return bSearch(sc, t, m - 1, e);
        else
            return bSearch(sc, t, s, m + 1);
    }

    /**
     * 倒序交换
     * 
     * @param arr
     */
    void swap(int[] arr) {
        int len = arr.length;
        for (int i = 0; i < len / 2; i++) {
            int temp = arr[i];
            arr[i] = arr[len - 1 - i];
            arr[len - 1 - i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] a = { 3, 2, 5, 7, 4, 6, 1, 8, 0, 9 };
        new SortAlgorithm().bubbleSort(a);
        String r = Arrays.toString(a);
        System.out.println(r);
        System.out.println(new SortAlgorithm().bSearch(a, 7, 0, 9));
    }
}
